#include <iostream>
#include <chrono>
#include "grafo.cpp"
#include "backtracking.cpp"
#include "goloso.cpp"
#include "dijkstra.cpp"
#include "local.cpp"


using namespace std;

int i; 
vector<Nodo> nodos;



void imprimir_solucion(vector <int> &solucion, int &w1, int &w2, bool solucion_encontrada)
{
	if (solucion_encontrada)
	{
		cout << w1 << " " << w2 << " " << solucion.size() << " " ;
	  for (int i = 0; i < solucion.size(); i++)
	  {
	    cout << solucion[i] << " ";
	  }	  
  }
  else 
  {
  	cout << "Existe camino, pero no se encontro ninguno";
  }
	cout << endl;		
}



void funcionPrincipal()
{
  nodos = crearGrafo();

  dijkstra();  

  if(distancia[v] > K)
  {	
  	cout << "No existe camino del vertice u al vertice v" << endl;
  	return;
  }

  auto start = chrono::high_resolution_clock::now();
  backtracking();
  auto finish = chrono::high_resolution_clock::now();
  cout << "Tiempo = " << chrono::duration_cast<chrono::microseconds>(finish - start).count() << "      Solucion Backtracking = ";
  imprimir_solucion(camino_u_v_backtracking, w1_backtracking, w2_backtracking, true);



  start = chrono::high_resolution_clock::now();
  bool solucion_encontrada = goloso();
  finish = chrono::high_resolution_clock::now();
  cout << "Tiempo = " << chrono::duration_cast<chrono::microseconds>(finish - start).count() << "      Solucion Goloso = ";
  imprimir_solucion(camino_u_v_goloso, w1_goloso, w2_goloso, solucion_encontrada);


  start = chrono::high_resolution_clock::now();
  local(camino_u_v_goloso); 
  finish = chrono::high_resolution_clock::now();
  cout << "Tiempo = " << chrono::duration_cast<chrono::microseconds>(finish - start).count() << "      Solucion Local = ";
  imprimir_solucion(camino_u_v_local, w1_local, w2_local, true);


  return;
}
	









int main()
{
	i = 0;
  while(cin.peek() != 48) {
  	i++;
  	cout << endl << "**** ENTRADA " << i << " ****" << endl;
    funcionPrincipal();
    cin.get();
  }
  return 0;
}